#include <iostream>
#include <iterator>
#include <vector>
#include <string>
#include <algorithm>
#include <istream>
#include <sstream>
#include "conio.h"
#include "assert.h"

using namespace std;

// Director-employee dsu
class Disjoint_set_union
{
public:
	Disjoint_set_union(int n_elements) : n_elems(n_elements),
		parent(n_elements),
		rank(n_elements, 0),
		real_root(n_elements)
	{
		for (int i_elem = 0; i_elem < n_elements; ++i_elem)
		{
			parent[i_elem] = i_elem;
			real_root[i_elem] = i_elem;
		}
	}

	int find(int n)
	{
		if (n != parent[n])
		{
			parent[n] = find(parent[n]);
		}
		return parent[n];
	}

	int get_director(int n)
	{
		return real_root[find(n)];
	}

	// union analog
	// set b director of a
	bool set_director(int a, int b)
	{
		int a_director = get_director(a),
			b_director = get_director(b);

		if (a_director != a || a_director == b_director)
			return false;

		if (rank[a_director] > rank[b_director])
		{
			parent[b_director] = a_director;
			real_root[a_director] = b;
		}
		else if (rank[b_director] > rank[a_director])
		{
			parent[a_director] = b_director;
		}
		else
			parent[a_director] = b_director;

		return true;
	}

private:
	int n_elems;
	vector<int> parent, rank, real_root;
};

int str2int(const string &str)
{
	istringstream in_ss(str);
	int res;
	in_ss >> res;
	return res;
}

void main()
{
	int n_employers;
	cout << "Input the number of employers: ";
	cin >> n_employers;

	int n_commands;
	cout << "Input the number of commands: ";
	cin >> n_commands;

	std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
	vector<string> commands(n_commands);
	cout << "Input commands: ";
	for (int i_c = 0; i_c < n_commands; ++i_c)
	{
		getline(cin, commands[i_c]);
	}

	cout << "Commands and their results: ";
	Disjoint_set_union dsu(n_employers);
	for (int i_c = 0; i_c < n_commands; ++i_c)
	{
		vector<string> tokens;
		istringstream iss(commands[i_c]);
		copy(istream_iterator<string>(iss),
			istream_iterator<string>(),
			back_inserter(tokens));

		cout << i_c << ") " << commands[i_c] << " : ";
		if (tokens.size() == 1)
		{
			cout << dsu.get_director(str2int(tokens[0])) << endl;
		}
		else if (tokens.size() == 2)
		{
			cout << dsu.set_director(str2int(tokens[0]), str2int(tokens[1])) << endl;
		}
		else
			assert(0);
	}

	//_getch();
	std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}